// 用于解决背包问题
function schoolBag(n, weight, profit) {
	const newArr = new Array(weight.length).fill(0).map((item, index) => {
		return {
			weight: weight[index],
			profit: profit[index],
		};
	});
	const length = newArr.length;
	// 重量从小到大排列
	newArr.sort((a, b) => {
		return a[weight] - b[weight];
	});
	// dp[i]表示当背包容量为i时，最多装多少价值的物品
	const dp = new Array(n + 1).fill(0).map((i) => {
		return {
			maxProfit: 0,
			// 记录当重量为i时，装入了哪些物品
			map: new Set(),
		};
	});

	// 构建dp
	for (let i = 1; i < n + 1; i++) {
		// 遍历之前的dp数组
		let thisProfit = 0;
		// 查找之前的dp，更新dp5
		for (let j = 0; j < length && newArr[j].weight <= i; j++) {
			// 取出当背包重量为i - newArr[j].weight时，装入了哪些物品的映射表
			const map = dp[i - newArr[j].weight].map;
			// 如果当前物品已经被装过了，那么就跳过
			if (map.has(j)) {
				continue;
			}
			// 正常的更新，不多解释
			if (
				dp[i - newArr[j].weight].maxProfit + newArr[j].profit >
				thisProfit
			) {
				// 拷贝一个set，防止引用统一个set
				const newMap = new Set(map);
				thisProfit =
					dp[i - newArr[j].weight].maxProfit + newArr[j].profit;
				dp[i].map = newMap;
				// 在对应的map中加入本次放入的物品
				newMap.add(j);
			}
		}
		dp[i].maxProfit = thisProfit;
	}

    // 返回最大重量
	// return [...dp[n].map].reduce((pre, cur) => {
    //     console.log(cur)
    //     return pre + newArr[cur].weight;
    // },0);

    // 返回最大利润
    return dp[n].maxProfit
}
console.log(schoolBag(10, [3, 4, 6, 5, 2], [6, 3, 5, 4, 1])); // 11
